FP In scala Chapter 2

See https://github.com/fpinscala/fpinscala/wiki/Chapter-2:-Getting-started for official notes.

Tail Recursion

Recursive function calls can be tail recursive if the last call of the function can be returns immediately. Scala will convert this into a while loop, and there will be not stack frame exhaustion. An example of a recursive call that is not tail recursive:

1 + go(n, acc)

In this case, even after having evaluated go(n, acc) the funcion result must be returned in order to be evaluated in the stack above. A tail call elimination can be made when there is no subsequent evaluation.

An annotation @annotation.tailrec can be added before the function call in order to catch any recursive functions that should but cannot be tail call eliminated.

Exercise 2.1



In [9]:

    
def fibTail(n: Int): Int = {

    @annotation.tailrec
    def go(n: Int, current: Int, fibCurrent: Int, fibPrevious: Int): Int = {

      if(n == current) return(fibCurrent)

      go(n, current + 1, fibCurrent + fibPrevious, fibCurrent)
    }

    if(n == 0) return(0)
     
    go(n, 1, 1, 0)

  }









    





defined function fibTail



In [4]:

    
fibTail(11)









    





res2: Int = 89

Markus Fib Note that he uses three arguments and counts down rather than up.



In [76]:

    
def fib(n: Int): Int = {
      @annotation.tailrec
      def loop(n: Int, currentFib: Int, nextFib: Int): Int = 
          if (n == 0) currentFib else loop(n-1, nextFib, currentFib + nextFib)
    
      if (n < 0) throw new IllegalArgumentException("fibonacci argument must be greater than 0")
      loop(n, 0, 1)
  }









    





defined function fib



In [16]:

    
(0 to 5).map(fib)









    





res14: scala.collection.immutable.IndexedSeq[Int] = Vector(0, 1, 1, 2, 3, 5)



In [14]:

    
(0 to 5).map(fibTail)









    





res12: scala.collection.immutable.IndexedSeq[Int] = Vector(0, 1, 1, 2, 3, 5)



In [11]:

    
def fibRunar(n: Int): Int = {
      @annotation.tailrec
      def go(n: Int, acc: Int, res: Int): Int =
          if (n == 0) res
          else go(n - 1, acc + res, acc)

      go(n, 1, 0)
  }









    





defined function fibRunar



In [ ]:

Polymorphic functions

monomorphic functions operate on one datatype
polymorphic functions operate on any datatype. This is a special case of polymorphism often referred to as parametric polymorphism.

Exercise 2.2



In [24]:

    
def isSorted[A](as: Array[A], ordered: (A,A) => Boolean): Boolean = {
    
    @annotation.tailrec
    def loop(n: Int): Boolean = {
        if(n >= as.length) true
        else if(ordered(as(n-1), as(n))) loop(n+1)
        else false
    }

    if(as.length == 1) return(true)
    loop(1)
}









    





defined function isSorted



In [25]:

    
isSorted(Array(1), (x: Int,y: Int) => x <= y)









    





res19: Boolean = true



In [26]:

    
isSorted(Array(1,2,3), (x: Int,y: Int) => x <= y)









    





res20: Boolean = true



In [27]:

    
isSorted(Array(1,6,5), (x: Int,y: Int) => x <= y)









    





res21: Boolean = false



In [28]:

    
isSorted(Array("AB", "B"), (x: String, y: String) => x <= y)









    





res22: Boolean = true



In [21]:

    
@annotation.tailrec
final def isSortedMarkus[A](as: Array[A], gt: (A,A) => Boolean): Boolean = {
      if (as.length < 2) true
      else if (gt(as.head, as.tail.head)) false
      else isSortedMarkus(as.tail, gt)
  }









    





defined function isSortedMarkus



In [83]:

    
isSortedMarkus(Array(1,6,5), (x: Int,y: Int) => x <= y)









    





res67: Boolean = false

Pro/Cons of inner loop versus using tail.head

According to Marc, the as.tail.head call might loop through the full list every time. Test it.



In [86]:

    
load.ivy("com.storm-enroute" %% "scalameter" % "0.7")









    



:: problems summary ::
:::: WARNINGS
	Unable to reparse com.github.alexarchambault.jupyter#jupyter-scala-api_2.10.5;0.2.0-SNAPSHOT from sonatype-snapshots, using Fri Jun 05 09:13:44 BST 2015

	Choosing sonatype-snapshots for com.github.alexarchambault.jupyter#jupyter-scala-api_2.10.5;0.2.0-SNAPSHOT

	Unable to reparse com.github.alexarchambault#ammonite-api_2.10.5;0.3.1-SNAPSHOT from sonatype-snapshots, using Thu Sep 10 11:28:42 BST 2015

	Choosing sonatype-snapshots for com.github.alexarchambault#ammonite-api_2.10.5;0.3.1-SNAPSHOT

	Unable to reparse com.github.alexarchambault.jupyter#jupyter-api_2.10;0.2.0-SNAPSHOT from sonatype-snapshots, using Mon Jun 01 01:53:32 BST 2015

	Choosing sonatype-snapshots for com.github.alexarchambault.jupyter#jupyter-api_2.10;0.2.0-SNAPSHOT



In [ ]:

Functions as values

When we define a function literal like (a, b) => a < b it's really just synctatic sugar for:

val lessThan = new Function2[Int, Int, Boolean] { 
    def apply(a: Int, b: Int) = a < b
}

Function2 is a scala trait (similar to interface or rather mixin), and has a function apply defined.

Partially applied functions

Partially appled functions versus currying

Currying functions changes the structure of how you have to call it. If we look at a function that takes two arguments: f(a: A, b: B): C and curry it, it will take one argument but return a function: g(a: A): B => C. Partially applying a function on the other hand will take a function the will take say two arguments f(a: A, b: B): C, and fix one of the argument b so the remaining function takes on argument: h(a: A): C.

Exercise 2.3



In [77]:

    
def curry[A,B,C](f: (A, B) => C): A => (B => C) = {
    a => b => f(a,b)
}









    





defined function curry



In [80]:

    
def add(x: Int, y: Int) = x + y









    





defined function add



In [82]:









    





res66: (Int, Int) => Int = <function2>



In [ ]:



In [36]:

    
add(2,3)









    





res30: Int = 5



In [37]:

    
val add3to = curry(add)(3)









    





add3to: Int => Int = <function1>



In [39]:

    
add3to(4)









    





res33: Int = 7

Curry implementation that's build in to scala:



In [47]:

    
val f = (a: Int, b: Int) => a + b
  
val curf = f.curried









    





f: (Int, Int) => Int = <function2>
curf: Int => (Int => Int) = <function1>



In [57]:

    
val bla = curf _









    





bla: () => Int => (Int => Int) = <function0>

Hmm? how about this one!



In [56]:

    
bla()(3)(3)









    





res47: Int = 6

Exercise 2.4



In [58]:

    
def uncurry[A,B,C](f: A => B => C): (A, B) => C = {
    (a, b) => f(a)(b)
}









    





defined function uncurry



In [59]:

    
val uncurriedAdd = uncurry(curry(add))









    





uncurriedAdd: (Int, Int) => Int = <function2>



In [61]:

    
uncurriedAdd(2,3)









    





res52: Int = 5

Exercise 2.5



In [71]:

    
def compose[A, B, C](f: B => C, g: A => B): A => C = 
    a => f(g(a))









    





defined function compose



In [72]:

    
def addQuotes(d: Int): String = "'" + d + "'"









    





defined function addQuotes



In [73]:

    
def add3AndCompose = compose(addQuotes, add3to)









    





defined function add3AndCompose



In [74]:

    
add3AndCompose(4)









    





res61: String = "'7'"



In [ ]: